﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Classes
{
    class GraphImpl : IGraphImpl
    {
        IList<City> cities;
        IList<Flight> flights;
        IList<City> citiesOfSpan;
        IList<Flight> flightsForSearch;
        //   IList<City> sequenceOfParentCities;
        IList<Flight> listOfFlights;
        IList<Flight> sequence;
        IList<City> theCitiesList;
        ListOfConnections listOfConnections;
        City theCityWeGoFrom;
        City theCityWeGoTo;
        IList<City> citiesInConnection;
        IList<Flight> flightsInConnection;
        /* Resulting arrays with distances to nodes and how to get there */
        /* Resulting arrays with distances to nodes and how to get there */
        //  public IList<int> distances;
        //public IList<City> path;
        /* Holds queue for the nodes to be evaluated */
        private IList<City> queue;
        //public IList<City> Queue
        //{
        //    get { return queue; }
        //    set { queue = value; }
        //}
        public GraphImpl()
        {

            citiesOfSpan = new List<City>();
            flights = new List<Flight>();
            cities = new List<City>();
            flightsForSearch = new List<Flight>();
            listOfFlights = new List<Flight>();
            sequence = new List<Flight>(); // GetARoutetoTheCity(City from, City to)
            theCitiesList = new List<City>(); //  public IList<City> GetCities(City city)

            citiesInConnection = new List<City>();
            flightsInConnection = new List<Flight>();
            listOfConnections = new ListOfConnections();
            //queue = new List<City>();
            queue = new List<City>();



            // public double[] dist { get; private set; }  I replace it with




        }
        public bool DoesThisCityExist(String cityName)
        {
            bool searched;
            if (cities.SingleOrDefault(x => x.Name == cityName) != null)
            {
                searched = true;
            }
            else
            {
                searched = false;
            }
            return searched;
        }
        public IList<City> GetCities()
        {
            return cities;
        }

        public City GetCityByName(String cityName)
        {
            if (DoesThisCityExist(cityName) != false)
            {
                City city = cities.Single(x => x.Name == cityName);
                return city;
            }
            else
            {
                return null;
            }
        }
        public void SetTheCityFrom(City v)
        {
            theCityWeGoFrom = v;
        }

        public void SetTheCityTo(City v)
        {
            theCityWeGoTo = v;

        }
        public IList<City> ReturnCityList()
        {
            return cities;
        }
        public bool IsEmpty()
        {
            return cities.Count == 0;
        }



        public void PurifyConnection(City to)
        {

        }
        public void AddCity(City c)
        {
            cities.Add(c);
        }
        public void AddFlight(City from, City to, int price)
        {	//PRE (to,from) is not contained in the graph

            from.AddFlight(to, price);
        }

        public bool ContainsCity(City city)
        {
            return cities.Contains(city);
        }

        public bool IsAdjacent(City startCity, City endCity)
        {
            bool isAdjacent = false;
            foreach (Flight f in startCity.Flights())
            {
                if (f.To == endCity)
                {
                    isAdjacent = true;
                }
            }
            return isAdjacent;

        }

        public IList<City> GetAdjacencies(City city)
        {
            IList<City> list = new List<City>();
            foreach (Flight f in city.Flights())
            {
                list.Add(f.To);
            }
            return list;

        }


        /* I don't know how to implement this shit and when to use it
         public IEnumerator<City> Cities()
         {
             throw new System.NotImplementedException();
         }
         */

        public int GetNoOfCities()
        {
            int i = cities.Count;
            return i;
        }

        public int GetNoOfFlights()
        {
            int numberOfFlights = 0;
            foreach (City c in this.cities)
            {

                numberOfFlights += c.Flights().Count;
            }
            return numberOfFlights;
        }
        public void Unmark()
        {
            for (int i = 0; i < cities.Count; i++)
                (cities[i]).Mark = false;
        }


        public void Bfs(City v)
        {
            Queue<City> q = new Queue<City>();
            v.Mark = true;
            q.Enqueue(v);
            int level = 0;
            while (q.Count != 0)
            {
                City w = q.Dequeue();
                Console.WriteLine(w.Name);

                if (w.Mark)
                {
                    level++;
                }

                Console.WriteLine("Level: " + level);
                IList<City> adj = GetAdjacencies(w);
                for (int i = 0; i < adj.Count; i++)
                {
                    City u = adj[i];
                    Console.WriteLine(u.Name);
                    if (!u.Mark)
                    {
                        u.Mark = true;
                        q.Enqueue(u);
                    }
                }
            }
        }
        public void setToNullListOfConnections()
        {
            listOfConnections = new ListOfConnections();
        }
        public ListOfConnections SearchForConnections(City weGoFrom, City weGoTo)
        {
            IList<City> visited = new List<City>();
            visited.Add(weGoFrom);
            SetTheCityFrom(weGoFrom);
            SetTheCityTo(weGoTo);
            listOfConnections = BreadthFirst(visited);
            SetTheCityFrom(null);
            SetTheCityTo(null);
            return listOfConnections;
        }
        public ListOfConnections BreadthFirst(IList<City> visited)
        {

            IList<City> adj = GetAdjacencies(visited.Last());
            foreach (City c in adj)
            {
                if (visited.Contains(c))
                {
                    continue;
                }
                if (c.Equals(theCityWeGoTo))
                {
                    visited.Add(c);
                    // connection.SetFlightList(flightsForConnection);
                    // listOfConnections.AddConnection(connection);
                    //  PrintPath(visited);
                    Connection connection = new Connection();
                    connection.MakeFlightsOfCities(visited);
                    listOfConnections.AddConnection(connection);


                    City f = visited.Last();
                    visited.Remove(f);
                    // break; now it does actually work work
                }
                foreach (City x in adj)
                    if (visited.Contains(x) || x.Equals(theCityWeGoTo))
                    {
                        continue;
                    }

                visited.Add(c);
                BreadthFirst(visited);
                City last = visited.Last();
                visited.Remove(last);
            }

            return listOfConnections;
        }



        public void Clear()
        {
            cities = new List<City>();
        }



        public void Dfs(City v)//normal version
        {
            v.Mark = true;
            Console.WriteLine(v.Name + " " + v.Country);
            ICollection<City> adj = GetAdjacencies(v);
            foreach (City u in adj)
            {
                if (u.Mark != true)
                {
                    Dfs(u);
                }
            }
        }



        public void Dijkstra(City startCity)
        {
            startCity.Distance = 0;
            startCity.Mark = true;
            foreach(City c in cities)
            {
                queue.Add(c);
            }
            queue.Remove(startCity);
            while(queue.Count > 0)
        }



            }
        
        private City GetNextVertex(City currentVertex)
        {
            int min = int.MaxValue;
            City nextCity = new City();

            /* Search through queue to find the next node having the smallest distance */
 
                foreach (City c in queue)
                {
                    if (c.Distance > currentVertex.Distance + currentVertex.Flights().SingleOrDefault(x => x.To == c).Price && c.Distance != 0)
                    {
                        c.Distance = currentVertex.Distance + currentVertex.Flights().SingleOrDefault(x => x.To == c).Price;
                        c.AddCityToPath(currentVertex);
                    }
                    if (c.Distance == 0)
                    {
                        continue;
                    }
                    if (c.Distance <= min)
                    {
                        min = c.Distance;
                        if (!c.Mark)
                            nextCity = c;
               
            return nextCity;
        }





















        public void DijkstraMethod(City theCity)
        {
            foreach (City c in cities)
            {
                queue.Add(c);
            }
            theCity.Distance = 0;
        }
      
        IList<City> path;
        //public void Dijkstra2(City startCity)
        //{

        //    DijkstraMethod(startCity);

        //   //;
        //    while(queue.Count > 0)
        //    {
        //        path = new List<City>();
        //        City u = GetNextVertex();
     
        //        foreach (City v in GetAdjacencies(u))
        //        {                   
        //            if (v.Distance > u.Distance + u.Flights().SingleOrDefault(x => x.To == v).Price)
        //            {
        //                v.Distance = u.Distance + u.Flights().SingleOrDefault(x => x.To == v).Price;
        //                v.AddCityToPath(u);
        //            }
        //        }
        //    }
        //}
        public void PrintPath(City startingCity)
        {
            Dijkstra(startingCity);
            foreach (City c in cities)
            {
                //Console.WriteLine(c.Distance);
                //if (c.Path != null)
                //{
                //    foreach (City q in c.Path)
                //    {
                //        Console.WriteLine(q.Name);
                        
                //    }
                //}
                Console.WriteLine("*******");
                Console.ReadLine();

            }
        }
    }
}

    
           
           

        

        public void Dijkstra(City startCity)
        {
            startCity.Distance = 0;
            startCity.Mark = true;
            //foreach (City c in cities)
            //{
            //    queue.Add(c);
            //}
            GetNextVertex(startCity);
            foreach(City  c in cities)
            {
                Console.WriteLine(c.Name + " " + c.Distance);
                Console.ReadLine();
            }
            //for (int i = 0; i < queue.Count; i++)
            //{
            //    City c = GetNextVertex(queue[i]);
            //    Console.WriteLine(i.Name + " " + i.Distance);
            //    Console.ReadLine();


                //    Console.WriteLine(queue[i].Name + " " + queue[i].Distance);
                //    foreach(City v in queue[i].Path)
                //    {
                //        Console.WriteLine(v.Name);
                //    }
                //    Console.WriteLine("********");
                //    Console.ReadLine();
                //}



            }
        
        //private City GetNextVertex(City currentVertex)
        //{
        //    int min = int.MaxValue;
        //    City nextCity = new City();

        //    /* Search through queue to find the next node having the smallest distance */
        //    foreach (City h in GetAdjacencies(currentVertex))
        //    {
        //        if (!queue.Contains(h))
        //        {
        //            queue.Add(h);
        //        }
        //        foreach (City c in queue)
        //        {
        //            if (c.Distance > currentVertex.Distance + currentVertex.Flights().SingleOrDefault(x => x.To == c).Price && c.Distance != 0)
        //            {
        //                c.Distance = currentVertex.Distance + currentVertex.Flights().SingleOrDefault(x => x.To == c).Price;
        //                c.AddCityToPath(currentVertex);
        //            }
        //            if (c.Distance == 0)
        //            {
        //                continue;
        //            }
        //            if (c.Distance <= min)
        //            {
        //                min = c.Distance;
        //                if (!c.Mark)
        //                    nextCity = c;
        //            }
        //        }
        //    }
        //    return nextCity;
        //}
//public void DijsktraMethod(City startCity)
        //{
        //    startCity.Distance = 0;

        //    foreach (City c in cities)
        //    {
        //        queue.Add(c);
        //    }
        //}
        //public City GetNextCity()
        //{
        //    Nullable<int> min = null;
        //    City cityOf = new City();

        //    /* Search through queue to find the next node having the smallest distance */
        //    foreach (City c in queue)
        //    {
        //        if (c.Distance <= min)
        //        {
        //            min = c.Distance;
        //            cityOf = c;
        //        }
        //    }

        //    queue.Remove(cityOf);

        //    return cityOf;

        //}
        //public void Dijkstra(City startingCity)
        //{
        //    DijsktraMethod(startingCity);

        //    while (queue.Count > 0)
        //    {
        //        City u = GetNextCity();

        //        /* Find the nodes that u connects to and perform relax */
        //        foreach (City c in GetAdjacencies(u))
        //        {

        //            /* Edge exists, relax the edge */
        //            if (u.Distance > c.Distance + u.Flights().SingleOrDefault(x => x.To.Equals(c)).Price)
        //            {
        //                c.Distance = u.Distance + u.Flights().SingleOrDefault(x => x.To.Equals(c)).Price;
        //                c.AddCityToPath(u);
        //            }
        //        }

        //    }
        //}
        //public void PrintPath(City startingCity)
        //{
        //    Dijkstra(startingCity);
        //    foreach (City c in queue)
        //    {
        //        Console.WriteLine(c.Distance);
        //    }
        //}